package luogu;


import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class A8802P2 {
    static int n;
    static int m;
    static int N=1050;
    static int M=10010;
    static int[] h=new int[N];
    static int[] e=new int[M];
    static int[] ne=new int[M];
    static int[] w=new int[M];
    static int idx=1;
    static boolean[] st=new boolean[N];
    static int[] time=new int[N];
    static int[] dist=new int[N];//最短路数组
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String[] s = read.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);
        String[] s1 = read.readLine().split(" ");
        //时间
        for(int i=1;i<=n;i++){
            time[i]=Integer.parseInt(s1[i-1]);
        }
        //录入边
        for(int i=1;i<=m;i++){
            String[] s2 = read.readLine().split(" ");
            int a=Integer.parseInt(s2[0]);
            int b=Integer.parseInt(s2[1]);
            int c=Integer.parseInt(s2[2]);
            //a到达b的时间等于c+time[b]
            add(a,b,c+time[b]);
            add(b,a,c+time[a]);
        }
        dijkStar();

        log.write(Integer.toString(dist[n]-time[n]));
        log.flush();
        //最后输出的时间应该减去到达N的time[N]
    }
    static void add(int a,int b,int c)
    {
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    static void dijkStar(){
        Arrays.fill(dist,0x3f3f3f3f);
        dist[1]=0;
        Queue<Integer> queue=new LinkedList<>();
        //入
        queue.offer(1);//距离，编号
        st[1]=true;//标记在队列中
        while(!queue.isEmpty()){
            int poll = queue.poll();

            //标记不在队列
            st[poll]=false;
            //更新
            for(int edge=h[poll];edge!=0;edge=ne[edge]){
                int end=e[edge];
                //如果到达ta
                if(dist[end]>dist[poll]+w[edge]){
                    //更新最短距离
                    dist[end]=dist[poll]+w[edge];
                    //加入队列
               if(!st[end]){
                   queue.offer(end);
                   st[end]=true;
               }
                }
            }
        }


        //将第一个
    }
}


